package 分类.BFS;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class 转盘锁 {
    public int openLock(String[] deadends, String target) {
        Set<String> deads=new HashSet<>();
        Set<String> visited=new HashSet<>();
        for (String deadend:deadends){
            deads.add(deadend);
        }
        int step=0;
        Queue<String> q=new LinkedList<>();
        q.offer("0000");
        visited.add("0000");
        while (!q.isEmpty()){
            int sz=q.size();
            for (int a=0;a<sz;a++){
                String s=q.poll();
                if(deads.contains(s)) continue;
                if(s.equals(target)) return step;
                for (int i=0;i<4;i++){
                    String cur=up(s,i);
                    if(!visited.contains(cur)){
                        q.offer(cur);
                        visited.add(cur);
                    }
                    String cur1=down(s,i);
                    if(!visited.contains(cur1)){
                        q.offer(cur1);
                        visited.add(cur1);
                    }
                }
            }

            step++;
        }
        return -1;
    }

    String up(String s,int i){
        char[] chars=s.toCharArray();
        if(chars[i]=='9'){
            chars[i]='0';
        }else {
            chars[i]+=1;
        }
        return new String(chars);
    }

    String down(String s,int  i){
        char[] chars=s.toCharArray();
        if(chars[i]=='0'){
            chars[i]='9';
        }else{
            chars[i]-=1;
        }
        return new String(chars);
    }

    public static void main(String[] args) {
        char[] chars={'9','0','1','1'};
        System.out.println(new String(chars));
    }
}
